◀ Prev · Parts · Full · Next ▶

minimize ∑ ∑ c ∈ ∈ C x c {\displaystyle \sum _{c\in C}x_{c}} subject to ∑ ∑ c ∈ ∈ C a s , c x c ≥ ≥ n s {\displaystyle \sum _{c\in C}a_{s,c}x_{c}\geq n_{s}} for all s in S (all ns items of size s are packed). x c ∈ ∈ { 0 , … … , n } {\displaystyle x_{c}\in \{0,\ldots ,n\}} for all c in C (there are at most n bins overall, so at most n of each individual configuration).

The configuration LP is an integer linear program, so in general it is NP-hard. Moreover, even the problem itself is generally very large: it has C variables and S constraints. If the smallest item size is eB (for some fraction e in (0,1)), then there can be up to 1/e items in each bin, so the number of configurations C ~ S1/e, which can be very large if e is small (if e is considered a constant, then the integer LP can be solved by exhaustive search: there are at most S1/e configurations, and for each configuration there are at most n possible values, so there are at most n S 1 / e {\displaystyle n^{S^{1/e}}} combinations to check. For each combination, we have to check S constraints, so the run-time is S ⋅ ⋅ n S 1 / e {\displaystyle S\cdot n^{S^{1/e}}} , which is polynomial in n when S, e are constant).cite-ref-2-7-1[7]

However, this ILP serves as a basis for several approximation algorithms. The main idea of these algorithms is to reduce the original instance into a new instance in which S is small and e is large, so C is relatively small. Then, the ILP can be solved either by complete search (if S, C are sufficiently small), or by relaxing it into a fractional LP.

◀ Prev · Parts · Full · Next ▶